package com.leetcode.study;

/**
 * 4. 寻找两个正序数组的中位数
 * https://leetcode.cn/problems/median-of-two-sorted-arrays/
 */
public class L4 {
    public static void main(String[] args) {

        int[] ar1 = new int[]{1, 2, 4, 7, 32};
        int[] ar2 = new int[]{4, 5, 18};

        System.out.println(10/8);
        //System.out.println(binarySearch(ar1,4));

        System.out.println(findMedianSortedArrays(ar1, ar2));
        //System.out.println(findMedianSortedArrays1(ar1, ar2));

    }

    /**
     * 二分法/折半查找 有序数组
     * @param a
     * @param temp
     * @return
     */
    public static int binarySearch(int[] a, int temp) {

        int l = 0;
        int r = a.length -1;

        while (l <= r) {
            int mid = (l + r) /2;

            if (temp == a[mid]) {
                return mid;
            } else if (temp > a[mid]) {
                l = mid + 1;
            } else if (temp < a[mid]) {
                r = mid - -1;
            }
        }

        return -1;
    }

    /**
     * 使用了冒泡排序导致 时间复杂度直接变成 m * n
     * 而题目中要求m + n 自然使用二分法
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public static double findMedianSortedArrays1(int[] nums1, int[] nums2) {

        int[] array = new int[nums1.length + nums2.length];

        System.arraycopy(nums1, 0, array, 0, nums1.length);
        System.arraycopy(nums2, 0, array, nums1.length, nums2.length);

        // 冒泡
        for (int i = 0; i < array.length; i++) {
            for (int j = i + 1; j < array.length; j++) {
                int a = array[i];
                int b = array[j];
                int temp;
                if (a > b) {
                    temp = a;
                    array[i] = b;
                    array[j] = temp;
                }

            }
        }

        int destPos = array.length % 2;

        if (array.length == 1) {
            return array[0];
        }
        int pos = array.length / 2;
        if (destPos == 1) { // 奇数长
            return (double) array[pos];
        } else if (destPos == 0) { // 偶数数长
            return ((double) array[pos - 1] + (double) array[pos]) / 2;
        }
        return 0;
    }


    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n1 = nums1.length;
        int n2 = nums2.length;

        // 为什么要把小的放前、大的放后？
        if (n1 > n2) {
            return findMedianSortedArrays(nums2, nums1);
        }
        // 计算两个数组平均大小
        int k = (n1 + n2 + 1)/2;
        int left = 0;
        // 右边一直都是最小的数组长度，为什么？
        int right = n1;

        while (left < right) {

            int m1 = left + (right - left) / 2;
            int m2 = k - m1;

            if (nums1[m1] < nums2[m2 - 1]) {
                left = m1 + 1;
            } else {
                right = m1;
            }
        }
        int m1 = left;
        int m2 = k - left;
        int c1 = Math.max(m1 <= 0 ? Integer.MIN_VALUE : nums1[m1 - 1], m2 <= 0 ? Integer.MIN_VALUE : nums2[m2 - 1]);

        if ((n1 + n2) % 2 == 1) {
            return c1;
        }
        int c2 = Math.min(m1 >= n1 ? Integer.MAX_VALUE : nums1[m1], m2 >= n2 ? Integer.MAX_VALUE : nums2[m2]);
        return (c1 + c2) * 0.5;
    }

}
